The problem can be found at the following link: Question Link
A simple and straightforward question, to find the minimum distance between two numbers, x and y, in an array,
- I traverse the array once. I maintain two variables,
lastX
andlastY
, which represent the most recent positions of x and y in the array. - I also maintain a variable
out
to store the minimum distance found so far. As I traverse the array, I updatelastX
andlastY
whenever I encounter x or y. If bothlastX
andlastY
have been updated, I calculate the distance and updateout
accordingly. - Finally, I return
out
, which represents the minimum distance between x and y. Ifout
remains equal toINT_MAX
, it means one of the numbers was not found in the array, and I return -1.
- Time Complexity:
O(n)
, wheren
is the number of elements in the array. - Auxiliary Space Complexity:
O(1)
, as we are using a constant amount of additional space.
class Solution {
public:
int minDist(int a[], int n, int x, int y) {
int lastX, lastY, out;
lastX = lastY = -1;
out = INT_MAX;
for(int i = 0; i < n; ++i) {
if(a[i] == x)
lastX = i;
if(a[i] == y)
lastY = i;
if(lastX != -1 && lastY != -1)
out = min(out, abs(lastX - lastY));
}
return out == INT_MAX ? -1 : out;
}
};
For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.
If you find this solution helpful, consider supporting us by giving a ⭐ star to the getlost01/gfg-potd repository.